package backTrack;

import java.util.*;

public class ds90 {
    public static void main(String[] args) {
        System.out.println(subsetsWithDup(new int[]{4,4,4,1,4}));
    }
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);
        int[] used = new int[nums.length];
        dfs(nums, path, ans, 0, used);
        return ans;
    }
    public static void dfs(int[] nums, List<Integer> path, List<List<Integer>> ans, int index, int[] used){
        if(index > nums.length)
            return;
        ans.add(new ArrayList<>(path));
        for (int i = index; i < nums.length; i++) {
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0)
                continue;
            path.add(nums[i]);
            used[i] = 1;
            dfs(nums, path, ans, i + 1, used);
            path.remove(path.size() - 1);
            used[i] = 0;
        }
    }

}
